# DP
# dp[i] 表示前 i 个字符构成的子串的 translateNum
# 两种情况：
# 1. 如果最后两个字符可以分开也可以合在一起，则  dp[i] = dp[i - 1] + dp[i - 2]。比如
#     1212
#     dp[3] 有两种情况 121 2 和 12 12，即 dp[3] = dp[2] + dp[1]
# 2. 如果最后两个字符只能分开，则 dp[i] = dp[i - 1]，比如
#     1234
#     dp[3] 只有一种情况 123 4，即 dp[3] = dp[2]
class Solution:
    def translateNum(self, num: int) -> int:
        if num < 10:
            return 1

        s = str(num)
        dpa = [0] * len(s)

        def dp(i: int) -> int:
            return 0 if i < 0 else dpa[i]

        dpa[0] = 1
        dpa[1] = 2 if int(s[0:2]) < 26 else 1

        i = 2
        while i < len(s):
            cp, ci = s[i-1], s[i]
            if cp > '2' or cp == '0':
                dpa[i] = dp(i - 1)
            elif cp == '1':
                dpa[i] = dp(i - 1) + dp(i - 2)
            elif ci > '5':
                dpa[i] = dp(i - 1)
            else:
                dpa[i] = dp(i - 1) + dp(i - 2)
            i += 1
        print(dpa)
        return dpa[-1]


solu = Solution()
print(solu.translateNum(25))  # 2
print(solu.translateNum(12258))  # 5
